package baseclass.e_tree;


import utils.TreeNode;

/**
 * //如果是层次遍历，复杂度是o(n)
 *
  求完全二叉树节点的个数，要求时间复杂度小于o(N)。
 	一颗高度为h的满二叉树，节点数为2^0+2^1+...+2^(h-1) = 2^h - 1.

  算法： 对于当前节点node，统计其左子树所在的层次level1.
 		统计其右孩子node.right的最左子树所在的高度level2
		如果level2 < level1,那么node的右孩子所在的子树必定是一个满二叉，
 				加上当前节点，是 1 <<( height - level2 -1) + 左孩子的个数
 		如果level2  = level1 , 那么node的左孩子所在的子树必定是一个满二叉，
 				加上当前节点，是 1 << (height - level1) + 右孩子的个数
 		递归此过程，最后访问的必定是最后一个层级的某个节点，所以是height = level
 */
public class Code10_FullBTNodeNumber {

	public static int nodeNum(TreeNode head) {
		if (head == null) {
			return 0;
		}
		return bs(head, 1, mostLeftLevel(head, 1));
	}

	public static int bs(TreeNode TreeNode, int level, int height) {
		//递归的终止条件。只剩一个节点，那么所在层数 = 树的总高度 ，统计节点数 + 1
		if (level == height) {
			return 1;
		}
		// 如果当前节点的右子树的最左节点所在的层级是 树的总高度，
		// 那么当前节点的左子树必定是一颗满二叉,子树高度是 height - level
		if (mostLeftLevel(TreeNode.right, level + 1) == height) {
			// 1 << (height - level) = 左子树的满二叉 + 当前节点  = 2^(height - level) -1  + 1
			// 左子树统计完，把节点给右孩子，递归当前行为
			return (1 << (height - level)) + bs(TreeNode.right, level + 1, height);
		} else {
			//如果当前节点的右子树的最左节点所在的层级树 是 树的总高度 - 1，
			// 那么当前节点的右子树必定是一颗满二叉，子树高度是 height - level - 1
			// 右子树统计完，把节点给左孩子，递归当前行为
			return (1 << (height - level - 1)) + bs(TreeNode.left, level + 1, height);
		}
	}

	//返回当前节点的左子树所在的层次高度
	private static int mostLeftLevel(TreeNode node, int level) {
		if(node == null) return level - 1;
		while (node.left != null) {
			level++;
			node = node.left;
		}
		return level;
	}

	public static void main(String[] args) {
		TreeNode head = new TreeNode(1);
		head.left = new TreeNode(2);
		head.right = new TreeNode(3);
		head.left.left = new TreeNode(4);
		head.left.left.left = new TreeNode(8);
		head.left.left.right = new TreeNode(9);
		head.left.right = new TreeNode(5);
		head.left.right.left = new TreeNode(10);
		head.left.right.right = new TreeNode(11);
		head.right.left = new TreeNode(6);
		head.right.right = new TreeNode(7);
		head.right.right.left = new TreeNode(14);
		head.right.left.left = new TreeNode(12);
		head.right.left.right = new TreeNode(13);
//		head.right. = new TreeNode(6);
		System.out.println(nodeNum(head));
	}

}
